package 剑指offer;



public class p36二叉搜索树与双向链表 {
    Node pre,head;
    public Node treeToDoublyList(Node root) {
        if (root==null) return null;

        //利用中序遍历，构造双向链表
        inOrder(root);

        //构造循环链表
        pre.right=head;
        head.left=pre;

        //返回 双向循环链表的头结点
        return head;
    }

    private void inOrder(Node cur) {
        if (cur==null) {
            //递归出口
            return;
        }
        inOrder(cur.left);

        //构造前驱结点和当前结点的指向关系
        if (pre==null) {
            head=cur;
        }else {
            //pre!=null
            pre.right=cur;
        }

        cur.left=pre;
        pre=cur;

        inOrder(cur.right);
    }
}
